package person.bing.fbcloud.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * TODO error
 * @author: mengfanbing
 * @date: 2020/9/3 9:33
 */
public class Q51 {
    public static void main(String[] args) {
        solveNQueens(4);
        System.out.println(ans);
    }
    static List<List<String>> ans = new ArrayList<>();

    public static List<List<String>> solveNQueens(int n) {
        List<Integer> usedCols = new ArrayList<Integer>();
        List<String> rows = new ArrayList<String>();
        util(usedCols, n, rows);
        /*for (int i=0;i<n;i++){
            List<Integer> usedCols = new ArrayList<Integer>();
            usedCols.add(i);
            List<String> rows = new ArrayList<String>();
            char[] chars = new char[n];
            Arrays.fill(chars,'.');
            chars[i] = 'Q';
            rows.add(new String(chars));
            util(usedCols, n, rows);
        }*/
        return ans;
    }
    public static void util2(int n) {
        List<String> rows = new ArrayList<String>();
        for (int i=0;i<n;i++){
            List<Integer> usedCols = new ArrayList<Integer>();
            usedCols.add(i);
            char[] chars = new char[n];
            Arrays.fill(chars,'.');
            chars[i] = 'Q';
            rows.add(new String(chars));
            util(usedCols, n, rows);
        }
    }

    public static void util(List<Integer> usedCols,int n,List<String> rows) {
        int rowsSize = rows.size();
        char[] chars = new char[n];
        Arrays.fill(chars,'.');
        int size = usedCols.size();
        if (rowsSize == n){
            ans.add(rows);
        }else if (rowsSize < n){
            boolean plusLeft = false;
            boolean plusRight = false;
            if (size > 0){
                Integer last = usedCols.get(size - 1);
                if (last-1 >= 0 && last-1 < n && !usedCols.contains(last-1)){
                    usedCols.add(last-1);
                    plusLeft = true;
                }
                if (last+1 >= 0 && last+1 < n && !usedCols.contains(last+1)){
                    usedCols.add(last+1);
                    plusRight = true;
                }
            }
            for (int i=0;i<n;i++){
                if (!usedCols.contains(i)){
                    if (plusLeft && plusRight){
                        usedCols.remove(size+1);
                        usedCols.remove(size);
                    }else {
                        if (plusRight || plusLeft){
                            usedCols.remove(size);
                        }
                    }
                    chars[i] = 'Q';
                    usedCols.add(i);
                    rows.add(new String(chars));
                    util(usedCols,n,rows);
                }
            }
        }

    }
}
